// https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
#include <iostream>

using namespace std;

class Solution {
public:
	// 这种递归的方法会超时，因为调用栈过大，导致超时
    int numWays(int n) {
		if(n == 0) return 1;
		if(n <= 2){
			return n;
		}
		return numWays(n-1) + numWays(n-2);
    }
	// 通过for循环，降低内存占用
	int numWays(int n) {
        if(n == 0) return 1;
        if(n <= 2){
			return n;
		}
        int dp[n+1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 2; i < n+1; i++){
            dp[i] = (dp[i-1] + dp[i-2])%1000000007;
        }
        return dp[n];
    }
};

int main(){
	Solution so;
	int n = 5;
	int sum = so.numWays(n);
	cout << "sum:" << sum << endl;
	return 0;
}